import java.util.Deque;
import java.util.LinkedList;

/**
 * 面试题 03.02. 栈的最小值
 * https://leetcode-cn.com/problems/min-stack-lcci/
 */
public class Solutions_mianshi_03_02 {
    public static void main(String[] args) {
        MinStack3 minStack = new MinStack3();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int res1 = minStack.getMin();  // output: -3
        System.out.println(res1);
        minStack.pop();
        int res2 = minStack.top();  // output: 0
        System.out.println(res2);
        int res3 = minStack.getMin();  // output: -2
        System.out.println(res3);
    }
}

class MinStack3 {
    // 双栈处理
    private Deque<Integer> stack;
    private Deque<Integer> stack2;

    /** initialize your data structure here. */
    public MinStack3() {
        // 一个记录元素栈，一个记录最小栈
        stack = new LinkedList<>();
        stack2 = new LinkedList<>();
        stack2.add(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        // stack2 存储 x 对应的最小值
        stack2.push(Math.min(x, stack2.peek()));
    }

    public void pop() {
        // 两个栈都做弹出操作
        stack.pop();
        stack2.pop();
    }

    public int top() {
        // 记录元素的栈，获取栈顶元素
        return stack.peek();
    }

    public int getMin() {
        // 最小值
        return stack2.peek();
    }
}
